public class LIS {
    // 最长上升子序列
    // https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int LIS (int[] arr) {
        // write code here
        if (arr.length == 0) {
            return 0;
        }
        // dp[i]表示以第i个位置为结尾的最长上升子序列的长度
        int[] dp = new int[arr.length];
        // 状态转移方程：遍历第i个位置之前的元素，然后看是否能和当前元素形成上升子序列
        // 如果可以，那么dp[i] = max(dp[i], dp[j]+1)
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
        }
        int ret = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                ret = Math.max(ret, dp[i]);
            }
        }
        return ret;
    }
}
